#define _CRT_SECURE_NO_WARNINGS 1

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <assert.h>


typedef int ListNodetype;

typedef struct ListNode {
	ListNodetype val;
	struct ListNode* next;
	struct ListNode* prev;
}ListNode;



ListNode* ListInit(ListNode* head)
{
	assert(head);
	head->val = -1;
	head->prev = head;
	head->next = head;
	return head;
}


ListNode* buyListNode(ListNodetype x)
{
	ListNode* tmp = (ListNode*)malloc(sizeof(ListNode));
	if (tmp == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	tmp->val = x;
	tmp->prev = NULL;
	tmp->next = NULL;
	return tmp;
}

void print(ListNode* head)
{
	while (head)
	{
		printf("%d->", head->val);
		head = head->next;
	}
	printf("NULL\n");
}

ListNode* Find(ListNode* head, ListNodetype x)
{
	while (head)
	{
		if (head->val == x)
		{
			return head;
		}
		head = head->next;
	}
	return NULL;
}

void ListInsert(ListNode* cur, ListNodetype x)
{
	assert(cur);
	ListNode* tmp = cur->prev;
	ListNode* node = buyListNode(x);
	tmp->next = node;
	node->prev = tmp;
	node->next = cur;
	cur->prev = node;
}

void Listpushfrist(ListNode* head, ListNodetype x)
{
	ListInsert(head->next, x);
}

void Listpushback(ListNode* head, ListNodetype x)
{
	ListInsert(head, x);
}

void ListErase(ListNode* cur)
{
	assert(cur);
	ListNode* tmp = cur->prev;
	ListNode* next = cur->next;
	free(cur);
	tmp->next = next;
	next->prev = tmp;
}

void Listpopfrist(ListNode* head)
{
	ListErase(head->next);
}

void Listpopback(ListNode* head)
{
	ListErase(head->prev);
}


ListNode* ListCreate()
{
	ListNode* node = buyListNode(1);
	ListNode* head = ListInit(node);
	return head;
}

void ListDestory(ListNode* head)
{
	ListNode* cur = head;
	while (cur)
	{
		ListNode* tmp = cur->next;
		free(cur);
		cur = tmp;
		if (cur == head)
		{
			break;
		}
	}
}

int main()
{
	ListNode* head = ListCreate();
	Listpushfrist(head, 1);
	Listpushfrist(head, 2);
	Listpushfrist(head, 3);
	Listpushback(head, 4);
	Listpushback(head, 5);
	//Listpopfrist(head);
	//Listpopback(head);

	ListNode* tmp = Find(head, 4);
	//ListErase(tmp);
	ListInsert(tmp, 6);

	ListDestory(head);




	//print(head);
	return 0;
}








//typedef struct ListNode {
//    int val;
//    struct ListNode* next;
//}ListNode;
//
//struct ListNode* Buysltnode(int n)
//{
//    struct ListNode* tmp = (struct ListNode*)malloc(sizeof(struct ListNode));
//    if (tmp == NULL)
//    {
//        perror("malloc Buysltnode");
//        exit(-1);
//    }
//    tmp->val = n;
//    tmp->next = NULL;
//    return tmp;
//}
//
//struct ListNode* Creatlist(int n, int arr[20])
//{
//    struct ListNode* front = NULL;
//    struct ListNode* tmp = NULL;
//    int i = 0;
//    for (i = 0; i < n; i++)
//    {
//        struct ListNode* new = Buysltnode(arr[i]);
//        if (new == NULL)
//        {
//            perror("malloc Buysltnode");
//            exit(-1);
//        }
//        if (front == NULL)
//        {
//            front = new;
//            tmp = new;
//        }
//        else
//        {
//            tmp->next = new;
//            tmp = tmp->next;
//        }
//    }
//    return front;
//}
//
//void SLTprint(struct ListNode* head)
//{
//    struct ListNode* tmp = head;
//    while (tmp)
//    {
//        printf("%d ", tmp->val);
//        tmp = tmp->next;
//    }
//    printf("\n");
//}
//
//int chkPalindrome(ListNode* A) {
//    // write code here
//    ListNode* slow = A;
//    ListNode* fast = A;
//    while (fast && fast->next)
//    {
//        slow = slow->next;
//        fast = fast->next->next;
//    }
//    ListNode* change = NULL;
//    ListNode* head = slow;
//    while (head)
//    {
//        ListNode* next = head->next;
//        head->next = change;
//        change = head;
//        head = next;
//    }
//    ListNode* cur = A;
//    while (cur && change)
//    {
//        if (cur->val != change->val)
//        {
//            return -1;
//        }
//        cur = cur->next;
//        change = change->next;
//    }
//    return 1;
//}
//
//int main()
//{
//    int arr1[20] = { 1,2,3,2,1 };
//    int arr2[20] = { 1,3,4 };
//    struct ListNode* new1 = Creatlist(5, arr1);
//    int a = chkPalindrome(new1);
//    printf("%d ", a);
//    //SLTprint(new1);
//
//
//    return 0;
//}


//int main() 
//{
//	int a = 2;
//	int b = 4;
//	int sum = abs(a - b);
//	printf("%d ", sum);
//	return 0;
//}




//typedef struct ListNode {
//    int val;
//    struct ListNode* next;
//}ListNode;
//
//struct ListNode* Buysltnode(int n)
//{
//    struct ListNode* tmp = (struct ListNode*)malloc(sizeof(struct ListNode));
//    if (tmp == NULL)
//    {
//        perror("malloc Buysltnode");
//        exit(-1);
//    }
//    tmp->val = n;
//    tmp->next = NULL;
//    return tmp;
//}
//
//struct ListNode* Creatlist(int n, int arr[20])
//{
//    struct ListNode* front = NULL;
//    struct ListNode* tmp = NULL;
//    int i = 0;
//    for (i = 0; i < n; i++)
//    {
//        struct ListNode* new = Buysltnode(arr[i]);
//        if (new == NULL)
//        {
//            perror("malloc Buysltnode");
//            exit(-1);
//        }
//        if (front == NULL)
//        {
//            front = new;
//            tmp = new;
//        }
//        else
//        {
//            tmp->next = new;
//            tmp = tmp->next;
//        }
//    }
//    return front;
//}
//
//void SLTprint(struct ListNode* head)
//{
//    struct ListNode* tmp = head;
//    while (tmp)
//    {
//        printf("%d ", tmp->val);
//        tmp = tmp->next;
//    }
//    printf("\n");
//}
//
//struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
//    struct ListNode* changeA = headA;
//    struct ListNode* changeB = headB;
//    int sumA = 0, sumB = 0;
//    while (changeA->next)
//    {
//        sumA += 1;
//        changeA = changeA->next;
//    }
//    while (changeB->next)
//    {
//        sumB += 1;
//        changeB = changeB->next;
//    }
//    if (changeA != changeB)
//    {
//        return NULL;
//    }
//    struct ListNode* fastlist = headA;
//    struct ListNode* slowlist = headB;
//    if (sumA < sumB)
//    {
//        fastlist = headB;
//        slowlist = headA;
//    }
//    int tmp = abs(sumA - sumB);
//    while (tmp--)
//    {
//        fastlist = fastlist->next;
//    }
//    while (fastlist && slowlist)
//    {
//        if (fastlist == slowlist)
//        {
//            return fastlist;
//        }
//        fastlist = fastlist->next;
//        slowlist = slowlist->next;
//    }
//}
//
//int main()
//{
//    int arr1[20] = { 1,2,3,4,5 };
//    int arr2[20] = { 5,6 };
//    struct ListNode* new1 = Creatlist(5, arr1);
//    struct ListNode* new2 = Creatlist(2, arr2);
//    //ListNode* cur = new1->next->next->next;
//    //new2->next->next = cur;
//    //SLTprint(new1);
//    //SLTprint(new2);
//    ListNode* end = getIntersectionNode(new1, new2);
//
//
//
//    return 0;
//}



